#include <stdio.h>
#include "tree.h"

typedef struct node List;
typedef struct node Node;
struct node {
    int data;
    Node *next;
};

void list_print(Node *node)
{
    if (node != NULL) {
        list_print(node->next);
        printf("%d ", node->data);
    }
}

void S004(Tree root, int val)
{
    static List head;

    if (root == NULL) {
        return;
    }

    if (val - root->data == 0) {
        list_print(head.next);
        printf("%d ", root->data);
        printf("\n");

        return;
    } else if (val - root->data > 0) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = root->data;
        node->next = head.next;
        head.next = node;
        S004(root->left, val - root->data);
        S004(root->right, val - root->data);
        head.next = head.next->next;
        free(node);
    } else {
        return;
    }
}


int main(int argc, const char *argv[])
{
    Tree root = tree_create(10);
    tree_insert(root, 5, intcomp);
    tree_insert(root, 12, intcomp);
    tree_insert(root, 4, intcomp);
    tree_insert(root, 7, intcomp);

    S004(root, 22);
    return 0;
}
